#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right)
        {
            leftMax = max(height[left], leftMax);
            rightMax = max(height[right], rightMax);
            if (height[left] < height[right])
                res += leftMax - height[left++];
            else
                res += rightMax - height[right--];
        }
        return res;
    }

    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n), rightMax(n);
        int res = 0;
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        for (int i = 1; i < height.size(); ++i)
            leftMax[i] = max(leftMax[i - 1], height[i]);
        for (int i = n - 2; i >= 0; --i)
            rightMax[i] = max(rightMax[i + 1], height[i]);
        for (int i = 0; i < n; ++i)
            res += min(leftMax[i], rightMax[i]) - height[i];
        return res;
    }
};